Search results for "Regular graph"
showing 10 items of 20 documents
Adjacency matrices of random digraphs: singularity and anti-concentration
2017
Let ${\mathcal D}_{n,d}$ be the set of all $d$-regular directed graphs on $n$ vertices. Let $G$ be a graph chosen uniformly at random from ${\mathcal D}_{n,d}$ and $M$ be its adjacency matrix. We show that $M$ is invertible with probability at least $1-C\ln^{3} d/\sqrt{d}$ for $C\leq d\leq cn/\ln^2 n$, where $c, C$ are positive absolute constants. To this end, we establish a few properties of $d$-regular directed graphs. One of them, a Littlewood-Offord type anti-concentration property, is of independent interest. Let $J$ be a subset of vertices of $G$ with $|J|\approx n/d$. Let $\delta_i$ be the indicator of the event that the vertex $i$ is connected to $J$ and define $\delta = (\delta_1, …
Incomplete vertices in the prime graph on conjugacy class sizes of finite groups
2013
Abstract Given a finite group G, consider the prime graph built on the set of conjugacy class sizes of G. Denoting by π 0 the set of vertices of this graph that are not adjacent to at least one other vertex, we show that the Hall π 0 -subgroups of G (which do exist) are metabelian.
Partially Square Graphs, Hamiltonicity and Circumference II
2000
Abstract Given a graph G, its partially square graph G∗ is a graph obtained by adding an edge uv for each pair u, v of vertices of G at distance 2 whenever the vertices u and v have a common neighbor x satisfying the condition NG(x) ⊆ NG[u] ∪ NG[v], where NG[x]= NG(x) ∪ {x}. In case G is a claw-free graph, G∗ is equal to G2, We define σ ∗ t = min{ ∑ x∈ d ∗ G (x): S is an independent set in G ∗ and ∣S∣ = t} , where d ∗ G (x) = ∣{y ∈ V∣ xy ∈ E(G∗)}∣ . We give for hamiltonicity and circumference new sufficient conditions depending on and we improve some known results.
Some properties of vertex-oblique graphs
2016
The type t G ( v ) of a vertex v ? V ( G ) is the ordered degree-sequence ( d 1 , ? , d d G ( v ) ) of the vertices adjacent with v , where d 1 ? ? ? d d G ( v ) . A graph G is called vertex-oblique if it contains no two vertices of the same type. In this paper we show that for reals a , b the class of vertex-oblique graphs G for which | E ( G ) | ? a | V ( G ) | + b holds is finite when a ? 1 and infinite when a ? 2 . Apart from one missing interval, it solves the following problem posed by Schreyer et?al. (2007): How many graphs of bounded average degree are vertex-oblique? Furthermore we obtain the tight upper bound on the independence and clique numbers of vertex-oblique graphs as a fun…
On the Soluble Graph of a Finite Simple Group
2013
The maximal independent sets of the soluble graph of a finite simple group G are studied and their independence number is determined. In particular, it is shown that this graph in many cases has an independent set with three vertices.
Degree sequences of highly irregular graphs
1997
AbstractWe call a simple graph highly irregular if each of its vertices is adjacent only to vertices with distinct degrees. In this paper we examine the degree sequences of highly irregular graphs. We give necessary and sufficient conditions for a sequence of positive integers to be the degree sequence of a highly irregular graph.
On the family ofr-regular graphs with Grundy numberr+1
2014
Abstract The Grundy number of a graph G , denoted by Γ ( G ) , is the largest k such that there exists a partition of V ( G ) , into k independent sets V 1 , … , V k and every vertex of V i is adjacent to at least one vertex in V j , for every j i . The objects which are studied in this article are families of r -regular graphs such that Γ ( G ) = r + 1 . Using the notion of independent module, a characterization of this family is given for r = 3 . Moreover, we determine classes of graphs in this family, in particular, the class of r -regular graphs without induced C 4 , for r ≤ 4 . Furthermore, our propositions imply results on the partial Grundy number.
Bounds for minimum feedback vertex sets in distance graphs and circulant graphs
2008
Graphs and Algorithms
P-matrix completions under weak symmetry assumptions
2000
An n-by-n matrix is called a Π-matrix if it is one of (weakly) sign-symmetric, positive, nonnegative P-matrix, (weakly) sign-symmetric, positive, nonnegative P0,1-matrix, or Fischer, or Koteljanskii matrix. In this paper, we are interested in Π-matrix completion problems, that is, when a partial Π-matrix has a Π-matrix completion. Here, we prove that a combinatorially symmetric partial positive P-matrix has a positive P-matrix completion if the graph of its specified entries is an n-cycle. In general, a combinatorially symmetric partial Π-matrix has a Π-matrix completion if the graph of its specified entries is a 1-chordal graph. This condition is also necessary for (weakly) sign-symmetric …
Groups whose prime graph on conjugacy class sizes has few complete vertices
2012
Abstract Let G be a finite group, and let Γ ( G ) denote the prime graph built on the set of conjugacy class sizes of G. In this paper, we consider the situation when Γ ( G ) has “few complete vertices”, and our aim is to investigate the influence of this property on the group structure of G. More precisely, assuming that there exists at most one vertex of Γ ( G ) that is adjacent to all the other vertices, we show that G is solvable with Fitting height at most 3 (the bound being the best possible). Moreover, if Γ ( G ) has no complete vertices, then G is a semidirect product of two abelian groups having coprime orders. Finally, we completely characterize the case when Γ ( G ) is a regular …